/*
 * heap.c
 *
 *  Created on: 2011-8-19
 *      Author: jfhu
 */
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include "heap.h"

#define min(a, b) a > b ? b : a

int findmin(pHeap h)
{
	if (h == NULL || h->size == 0) {
		printf("heap:findmin: The input heap is NULL or Empty\n");
		return -1;
	}

	return h->arr[0];
}

void insert(int i, pHeap h)
{
	siftup(i, h->size, h);
	h->size++;
}

int deletemin(pHeap h)
{
	int i;
	if (h == NULL || h->size == 0)
		return -1;

	i = h->arr[0];

	siftdown(h->arr[h->size - 1], 0, h);

	h->size--;
	return i;
}

/*void delete(int i, pHeap h)
{
	int j = h->arr[h->size - 1];

	--h->size;

	if (i == j)
		return;

	if (i > j) {
		siftup(j, )
	} else {
		siftdown(j)
	}
}
*/

/* Sift up */
void siftup(int i, int x, pHeap h)
{
	int p = (x - 1) / h->d;
	while (x > 0 && h->arr[p] > i) {
		h->arr[x] = h->arr[p];
		x = p;
		p = (x - 1) / h->d;
	}

	h->arr[x] = i;
}

/* Sift down */
void siftdown(int i, int index, pHeap h)
{
	int c = minchild(index, h);

	while (c != -1 && h->arr[c] < i) {
		h->arr[index] = h->arr[c];
		index = c;
		c = minchild(index, h);
	}

	h->arr[index] = i;
}


/* Minimum children value */
int minchild(int index, pHeap h)
{
	int startIndex, endIndex, minchildvalue, minindex, i;

	startIndex = h->d * index + 1;
	endIndex = min(h->d * (index + 1), h->size - 1);

	if (startIndex > endIndex)
		return -1;

	minchildvalue = h->arr[startIndex];
	minindex = startIndex;
	for (i = startIndex + 1; i <= endIndex; i++) {
		if (h->arr[i] < minchildvalue) {
			minchildvalue = h->arr[i];
			minindex = i;
		}
	}
	return minindex;
}

pHeap makeheap(int *ary, int n, int d)
{
	int i;
	pHeap h = (pHeap)malloc(sizeof(heap));
	h->arr = (int *)malloc(sizeof(int) * n);
	h->size = n;
	h->capacity = n;
	h->d = d;
	i = 0;
	for (;i < n; i++) {
		h->arr[i] = ary[i];
	}

	for (i = n - 1; i >= 0; --i) {
		siftdown(h->arr[i], i, h);
	}
	return h;
}


/* Print the string of heap */
void printfHeap(const pHeap h)
{
	int i;
	printf("Capacity: %d,Size: %d, d: %d\n", h->capacity, h->size, h->d);

	for (i = 0; i < h->size; i++) {
		printf("%d ", h->arr[i]);
	}
	printf("\n");
}

/* Destroy heap */
void destroyHeap(pHeap h)
{
	if (h != NULL && h->arr != NULL) {
		free(h);
		free(h->arr);
		h = NULL;
	}
}
